﻿using System;
using System.Collections.Generic;
using System.Drawing;

namespace GridRegulator
{
    class TileMatcher : IPetGrid
    {
    /* variables */
        // constants
        const double kSadThr = 40;
        const double kForcedSadThr = 60;
        const int kV = 2;
        const int kV2 = 3;
        const int kV3 = 4;
        const int kVPoint1 = 6;
        const int kVPoint2 = 10;
        const int kDiffThr = 2;


        GrayImage mGray = null; 
        double[,] mCpxGrid = null;
        int[,] mPetGrid = null;
        PetList mPetList = new PetList();


        // i-component
        double mY0 = 0;
        double mHWidth = 0;
        int mYN = 0;

        // j-component
        double mX0 = 0;
        double mVWidth = 0;
        int mXN = 0;

        // base
        int mVBeginI = 0;
        int mHBeginI = 0;
        int mVEndI = 0;
        int mHEndI = 0;

        int mVCoreWidth = 0;
        int mHCoreWidth = 0;

    /* properties */

        /* for IPetGrid */
        public PetList Pets
        {
            get
            {
                return mPetList;
            }
        }

        /* for IPetGrid */
        public int this[int i, int j]
        {
            get
            {
                i += mHBeginI;
                j += mVBeginI;
                if (mPetGrid[i, j] > 0)
                    return mPetGrid[i, j] - 1;
                else
                    return -1;
            }
        }

        /* for IPetGrid */
        public int N    /* number of tiles in horizontal direction */
        {
            get
            {
                return mVEndI - mVBeginI;
            }
        }
        /* for IPetGrid */
        public int M    /* number of tiles in vertical direction */
        {
            get
            {
                return mHEndI - mHBeginI;
            }
        }

        public int TileWidth
        {
            get
            {
                return (int)Math.Round(mVWidth);
            }
        }
        public int TileHeight
        {
            get
            {
                return (int)Math.Round(mHWidth);
            }
        }

        public int JToX(int j)
        {
            return GetX(j + mVBeginI);
        }
        public int IToY(int i)
        {
            return GetY(i + mHBeginI);
        }

    /* methods */

        public TileMatcher()
        {
            Reset();
        }

        int GetX(int j)
        {
            return (int)Math.Round(mX0 + mVWidth * j);
        }
        int GetY(int i)
        {
            return (int)Math.Round(mY0 + mHWidth * i);
        }

        int GetCoreX(int j)
        {
            return (int)Math.Round(mX0 + mVWidth * j + mVWidth * 1.0 / 6.0);
        }
        int GetCoreY(int i)
        {
            return (int)Math.Round(mY0 + mHWidth * i + mHWidth * 1.0 / 6.0);
        }

        void Reset()
        {
            mGray = null;
            mCpxGrid = null;
            mPetGrid = null;
            mPetList.Clear();

            // i-component
            mY0 = 0;
            mHWidth = 0;
            mYN = 0;

            // j-component
            mX0 = 0;
            mVWidth = 0;
            mXN = 0;

            // base
            mVBeginI = 0;
            mHBeginI = 0;
            mVEndI = 0;
            mHEndI = 0;

            mVCoreWidth = 0;
            mHCoreWidth = 0;
        }

        void ClearData()
        {
            mCpxGrid = new double[mYN, mXN];
            mPetGrid = new int[mYN, mXN];

            for (int i = 0; i < mYN; i++)
            {
                for (int j = 0; j < mXN; j++)
                {
                    mCpxGrid[i, j] = -1;
                    mPetGrid[i, j] = -1;
                }
            }

            mPetList.Clear();
        }

        void GetComplexity()
        {
            double maxcomplexity = 0;
            for (int i = 0; i < mYN; i++)
            {
                int y = GetCoreY(i);
                bool yin = (i >= mHBeginI) && (i < mHEndI);

                for (int j = 0; j < mXN; j++)
                {
                    int x = GetCoreX(j);
                    bool xin = (j >= mVBeginI) && (j < mVEndI);

                    double complexity = ImageEvaluator.ImageComplexity(mGray, y, x, mHCoreWidth, mVCoreWidth);
                    mCpxGrid[i, j] = complexity;

                    if (yin && xin)
                    {
                        if (complexity > maxcomplexity)
                        {
                            maxcomplexity = complexity;
                        }
                    }
                }
            }

            /* wipe out ineligible */
            for (int i = 0; i < mYN; i++)
            {
                for (int j = 0; j < mXN; j++)
                {
                    if (mCpxGrid[i, j] > maxcomplexity * 1.5 || mCpxGrid[i, j] < maxcomplexity * 0.2)
                    {
                        mCpxGrid[i, j] = 0;
                    }
                }
            }
        }

        int GetMaxComplexity(int trynum, out int[] il, out int[] jl)
        {
            jl = new int[trynum];
            il = new int[trynum];
            double[] xl = new double[trynum];
            int n = 0;

            for (int i = mHBeginI; i < mHEndI; i++)
            {
                for (int j = mVBeginI; j < mVEndI; j++)
                {
                    for (int k = 0; k < xl.Length; k++)
                    {
                        if (mCpxGrid[i, j] > xl[k] && mCpxGrid[i, j] > 0)
                        {
                            for (int t = xl.Length - 1; t > k; t--)
                            {
                                xl[t] = xl[t - 1];
                                il[t] = il[t - 1];
                                jl[t] = jl[t - 1];
                            }
                            xl[k] = mCpxGrid[i, j];
                            il[k] = i;
                            jl[k] = j;

                            if (n < trynum)
                            {
                                n++;
                            }
                            break;
                        }
                    }
                }
            }
            return n;
        }


        double AppxSearch(int bi, int bj, out int di, out int dj, double thr)
        {
            double minsad = double.MaxValue;

            int y0 = GetCoreY(bi);
            int x0 = GetCoreX(bj);

            di = dj = -1;

            /* search within base */
            for (int i = mHBeginI; i < mHEndI; i++)
            {
                for (int j = mVBeginI; j < mVEndI; j++)
                {
                    if (bi == i && bj == j)
                        continue;

                    if (mCpxGrid[i,j] == 0)
                        continue;

                    int y1 = GetCoreY(i);
                    int x1 = GetCoreX(j);

                    double sad = ImageEvaluator.ImageSAD(mGray, y0, x0, mHCoreWidth, mVCoreWidth, y1, x1, kV);

                    if (sad < minsad)
                    {
                        minsad = sad;
                        di = i;
                        dj = j;
                    }
                }
            }

            if (minsad < thr)
            {
                return minsad;
            }

            /* search outside base */

            for (int i = 0; i < mYN; i++)
            {
                for (int j = 0; j < mXN; j++)
                {
                    if (i >= mHBeginI && i < mHEndI && j >= mVBeginI && j < mVEndI)
                        continue;

                    if (mCpxGrid[i, j] == 0)
                        continue;

                    int y1 = GetCoreY(i);
                    int x1 = GetCoreX(j);

                    double sad = ImageEvaluator.ImageSAD(mGray, y0, x0, mHCoreWidth, mVCoreWidth, y1, x1, kV);

                    if (sad < minsad)
                    {
                        minsad = sad;
                        di = i;
                        dj = j;
                    }
                }
            }

            return minsad;
        }

        double AppxMatch(int bi, int bj, int di, int dj, int v)
        {
            int y0 = GetCoreY(bi);
            int x0 = GetCoreX(bj);

            int y1 = GetCoreY(di);
            int x1 = GetCoreX(dj);

            return ImageEvaluator.ImageSAD(mGray, y0, x0, mHCoreWidth, mVCoreWidth, y1, x1, v);
        }

        bool AccurateMatch(int bi, int bj, int di, int dj, int v)
        {
            int x0 = GetCoreX(bj);
            int y0 = GetCoreY(bi);
            int x1 = GetCoreX(dj);
            int y1 = GetCoreY(di);

            return ImageEvaluator.HardCompare(mGray, y0, x0, mHCoreWidth, mVCoreWidth, y1, x1, v, kDiffThr);
        }

        bool AccurateMatch(int bi, int bj, int di, int dj)
        {
            return AccurateMatch(bi, bj, di, dj, kV);
        }

        bool UpdateBase(int i, int j)
        {
            bool changed = false;

            if (i < mHBeginI)
            {
                mHBeginI = i;
                changed = true;
            }
            else if (i >= mHEndI)
            {
                mHEndI = i + 1;
                changed = true;
            }
            if (j < mVBeginI)
            {
                mVBeginI = j;
                changed = true;
            }
            else if (j >= mVEndI)
            {
                mVEndI = j + 1;
                changed = true;
            }

            return changed;
        }

        bool GroupMatch()
        {
            mPetList.Clear();
            
            bool changed = true;
            List<Pos> badlist = new List<Pos>();

            while (changed)
            {
                int hbegini = mHBeginI;
                int vbegini = mVBeginI;
                int hendi = mHEndI;
                int vendi = mVEndI;

                changed = false;

                for (int i = hbegini; i < hendi; i++)
                {
                    for (int j = vbegini; j < vendi; j++)
                    {
                        if (mCpxGrid[i, j] <= 0)
                        {
                            continue;
                        }
                        if (mPetGrid[i, j] > 0 || mPetGrid[i, j] == -2)
                        {
                            continue;
                        }

                        Pet currpet = null;
                        for (int di = 0; di < mYN; di++)
                        {
                            bool iinbase = di >= hbegini && di < hendi;
                            for (int dj = 0; dj < mXN; dj++)
                            {
                                if (di == i && dj == j) continue;

                                int dd = Math.Max(Math.Abs(di - i), Math.Abs(dj - j));
                                int matchv = dd > kVPoint1 ? (dd > kVPoint2? kV3 : kV2) : kV;

                                bool match = AccurateMatch(i, j, di, dj, matchv);

                                if (match)
                                {
                                    if (currpet == null)
                                    {
                                        currpet = new Pet();
                                        currpet.Add(new Pos(i, j));
                                        mPetList.Add(currpet);
                                        mPetGrid[i, j] = mPetList.Count;
                                    }
                                    currpet.Add(new Pos(di, dj));
                                    mPetGrid[di, dj] = mPetList.Count;

                                    changed = UpdateBase(di, dj) || changed;
                                }
                            }
                        }

                        if (currpet == null)
                        {   // no match under strict comparison
                            mPetGrid[i, j] = -2;
                            badlist.Add(new Pos(i, j));
                        }
                    }
                }
            }   /* while(changed) */

            // deal with odds

            for (int ipet = 0; ipet < mPetList.Count && badlist.Count > 0; ipet++)
            {
                Pet pet = mPetList[ipet];
                if (pet.Count % 2 == 1)
                {
                    double smin = double.MaxValue;
                    int imin = -1;
                    for (int i = 0; i < badlist.Count; i++ )
                    {
                        Pos badpos = badlist[i];
                        double s = AppxMatch(pet[0].I, pet[0].J, badpos.I, badpos.J, kV);
                        if (s < smin)
                        {
                            smin = s;
                            imin = i;
                        }
                    }
                    pet.Add(new Pos(badlist[imin].I, badlist[imin].J));
                    mPetGrid[badlist[imin].I, badlist[imin].J] = ipet + 1;
                    badlist.RemoveAt(imin);
                }
            }

            if (badlist.Count == 2)
            {
                Pet pet = new Pet();
                mPetList.Add(pet);
                foreach (Pos badpos in badlist)
                {
                    pet.Add(badpos);
                    mPetGrid[badpos.I, badpos.J] = mPetList.Count;
                }
            }

            return true;
        }

        public bool ArrangePetList()
        {
            if (mPetList.Count == 0)
            {
                return false;
            }

            mHBeginI = int.MaxValue;
            mVBeginI = int.MaxValue;
            mHEndI = 0;
            mVEndI = 0;
            for (int i = 0; i < mPetList.Count; i++)
            {
                Pet pet = mPetList[i];
                for (int j = 0; j < pet.Count; j++)
                {
                    Pos pos = pet[j];
                    if (pos.I < mHBeginI) 
                        mHBeginI = pos.I;
                    if (pos.I + 1 > mHEndI) 
                        mHEndI = pos.I + 1;
                    if (pos.J < mVBeginI) 
                        mVBeginI = pos.J;
                    if (pos.J + 1 > mVEndI) 
                        mVEndI = pos.J + 1;
                }
            }

            for (int i = 0; i < mPetList.Count; i++)
            {
                Pet pet = mPetList[i];
                for (int j = 0; j < pet.Count; j++)
                {
                    Pos pos = pet[j];
                    pos.I -= mHBeginI;
                    pos.J -= mVBeginI;
                    pet[j] = pos;
                }
                pet.Sort();
            }

            return true;
        }

        bool SyncGrid(Bitmap image)
        {
            mGray = ColorConverter.BitmapToGray(image);

            int vbeginp, vendp, vn;
            int hbeginp, hendp, hn;
            LineLocator.Sync(mGray, out vbeginp, out vendp, out vn, 
                out hbeginp, out hendp, out hn);

            // TODO: refining synchroniztion to enhance detection
            //       ...

            if (vn < 2 || hn < 2)
            {
                // grid is not detectable
                return false;
            }

            mVWidth = ((double)(vendp - vbeginp)) / vn;
            mHWidth = ((double)(hendp - hbeginp)) / hn;
            mVCoreWidth = (int)Math.Round(mVWidth * 2 / 3);
            mHCoreWidth = (int)Math.Round(mHWidth * 2 / 3);


            mVBeginI = (int)(vbeginp / mVWidth);
            mHBeginI = (int)(hbeginp / mHWidth);
            mVEndI = mVBeginI + vn;
            mHEndI = mHBeginI + hn;
            mX0 = vbeginp - mVBeginI * mVWidth;
            mY0 = hbeginp - mHBeginI * mHWidth;
            mXN = (int)((mGray.Width - mX0) / mVWidth);
            mYN = (int)((mGray.Height - mY0) / mHWidth);

            return true;
        }

        public bool Match(Bitmap image)
        {
            /* 1. Grid Estimation */
            bool sync = SyncGrid(image);
            if (!sync)
            {
                Reset();
                return false;
            }

            /* 2. base complexity analysis */
            ClearData();
            GetComplexity();

            /* 3. adjustment (unused) */

            /* 4. Group Matching */
            bool grouped = GroupMatch();
            if (!grouped)
            {
                Reset();
                return false;
            }

            /* 5. Reorganize Pet list */
            bool arranged = ArrangePetList();
            if (!arranged)
            {
                Reset();
                return false;
            }

            return true;
        }

        public override string ToString()
        {
            String s = "";
            for (int i = 0; i < M; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    int v = this[i, j];
                    if (v < 0) s += String.Format("-1");
                    else s += String.Format("{0:d2}", v);
                    if (j < N - 1) s += ",";
                }
                s += "},\n";
            }
            return s;
        }

    }
}
